// 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

// 每行的元素从左到右升序排列。
// 每列的元素从上到下升序排列。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
using namespace std;

// 暴力法

// 执行用时：
// 1208 ms
// , 在所有 C++ 提交中击败了
// 5.01%
// 的用户
// 内存消耗：
// 14.5 MB
// , 在所有 C++ 提交中击败了
// 60.76%
// 的用户

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int len = matrix.size();
        
        if(len<1){
            return false;
        }
        int k = matrix[0].size();
        int begin;
        int end;
        int res;
        for(int i=0;i<len;i++){
            begin = matrix[i][0];
            end = matrix[i][k-1];
            if(begin<=target && end>=target){
                res =i;
                for(int j=0;j<k;j++){
                    if(matrix[res][j]==target){
                        return true;
                    }
                }
            }
        }
        return false;
    }
};